/**
 * @program: bagproblem
 * @author: JCM
 * @create: 2023-03-23 09:54
 * @description:
 **/
public class BagProblem {
    public static void main(String[] args) {
        int[] weight = {1,3,4};
        int[] value = {15,20,30};
        int bagSize = 4;
//        solve(weight,value,bagSize);
        solve1(weight,value,bagSize);
    }

    // 二维 dp
    private static void solve(int[] weight, int[] value, int bagSize) {
        // 1. 创建 dp 数组
        int goods = weight.length;
        int[][] dp = new int[goods][bagSize+1];
        // 2. 初始化 dp
        for (int j = weight[0];j < bagSize+1; j++) {
            dp[0][j] = value[0];
        }
        // 3. 填充 dp
        for (int i = 1; i < weight.length; i++) {
            for (int j = 1; j <= bagSize; j++) {
                if (j < weight[i]) {
                    // 背包容量小于物品重量
                    dp[i][j] = dp[i][j-1];
                }else {
                    // 背包容量大于等于物品重量
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-weight[i]]+value[i]);
                }
            }
        }
        // 打印 dp
        for (int i = 0; i < goods; i++) {
            for (int j = 0; j <= bagSize; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println("\n");
        }
    }
    // 一维 dp
    private static void solve1(int[] weight, int[] value, int bagSize) {
        // 1. 创建 dp
        int wLen = weight.length;
        int[] dp = new int[bagSize+1];
        // 2. 填充 dp
        for (int i = 0; i < wLen; i++) {
            for (int j = bagSize; j >= weight[i] ; j--) {
                dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);
            }
        }
        // 3. 打印 dp
        for (int j = 0; j <= bagSize; j++) {
            System.out.print(dp[j]+" ");
        }
    }
}
